import java.util.ArrayList;
import java.util.Arrays;

/**
 * Created whit IntelliJ IDEA.
 * Description：
 * User：ZHONGCHEN
 * Date:2022-04-19
 * Time:18:37
 */
public class TestDemo {
    //821. 字符的最短距离
    public int[] shortestToChar(String s, char c) {
        int[] ans = new int[s.length()];
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == c) {
                list.add(i);
            }
            ans[i] = Integer.MAX_VALUE;
        }
        for (int i = 0; i < s.length(); i++) {
            for (Integer num : list) {
                if (Math.abs(num - i) < ans[i]) {
                    ans[i] = Math.abs(num - i);
                }
            }
        }
        return ans;
    }

    //两次遍历，第一次找到每个 ii 左边最近的 c，第二次找到每个 ii 右边最近的 c
    public static int[] shortestToChar1(String s, char c) {
        int n = s.length();
        int[] ans = new int[n];
        Arrays.fill(ans, n + 1);
        for (int i = 0, j = -1; i < n; i++) {
            if (s.charAt(i) == c) {
                j = i;
            }
            if (j != -1) {
                ans[i] = i - j;
            }
        }
        for (int i = n - 1, j = -1; i >= 0; i--) {
            if (s.charAt(i) == c) {
                j=i;
            }
            if (j != -1) {
                ans[i] = Math.min(ans[i],j-i);
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        String s="loveleetcode";
        char c = 'e';
        System.out.println(shortestToChar1(s,c));
    }
}
